In a finite-dimensional vector space, the length of every linearly independent list of vectors is less than or equal to the length of every spanning list of vectors.
Suppose that \({latex.inline[u_{1}, ..., u_{m}](u_{1}, ..., u_{m})} is linearly independent in V. Suppose also that \){latex.inlinew{1}, ..., w{n}} spans V. We need to prove that ${latex.inlinem \leq n}. We do so through the process described below with m steps; note that in each step we add one of the u’s and remove one of the w’s.
Step 1: Let B be the list \({latex.inline[w_{1}, ..., w_{n}](w_{1}, ..., w_{n})} which spans V. Adjoining \){latex.inlineu_{1}} at the beginning of the list produces a linearly dependent list because \({latex.inline[u_{1}](u_{1})} can be written as a linear combination of the w’s(since w’s span V and \){latex.inlineu_{1} \in V}). In other words, the list \({latex.inline[u_{1}, w_{1}, ..., w_{n}](u_{1}, w_{1}, ..., w_{n})} is linearly _dependent_. Now we can use the linear dependence lemma. One of the vectors in the list above is a linear combination of the previous vectors in the list. We know that \){latex.inlineu_{1}} is not 0 because the list of u’s is linearly independent. Thus ${latex.inlineu_{1}} is not in the span of the previous vectors in the list above. Hence we can remove one of the w’s.
Step k for k = 2...m: The list B of length(n) from step k-1 spans V. In particular, \({latex.inline[u_{k}](u_{k})} is in the span of the list B. Thus the list of length(n + 1) obtained by adjoining \){latex.inlineu_{k}} to B, placing it just after \({latex.inline[u_{1}, ..., u_{k-1}](u_{1}, ..., u_{k-1})} is linearly dependent. By the linear dependence lemma, one of the vectors in this list is in the span of the previous ones, and because \){latex.inlineu{1}, ..., u{k}} is linearly independent, the vector cannot be one of the u’s.
Hence there must still be at least one remaining w at this step. We can remove from our new list(after adjoining \({latex.inline[u_{k}](u_{k})} at th eproper place) a w that is a linear combination of the prevoius vectors in the list, so that the new list B consisting of \){latex.inlineu{1}, ..., u{k}} and the remaining w’s spans V.
After step m, we have added all the u’s and the process stops. At each step we add a u to B, the linear dependence lemma implies there is some w to remove. Thus there are as many w’s as u’s.